#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution01 {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        // 先把负数取反
        // 然后选择最小的数进行取反
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto e : nums) 
            pq.push(e);
        // while (!pq.empty()) {
        //     // sum += pq.top();
        //     cout << pq.top() << endl;
        //     pq.pop();
        // }        
        while (k--) {
            int x = pq.top();
            pq.pop();
            x = -x;
            pq.push(x);
        }
        int sum = 0;
        while (!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
        return sum;
        return 0;
    }
};

class Solution02 {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        vector<int> nums;
        int n = heights.size();
        for (int i = 0; i < n; i++)
            nums.push_back(i);
        QS(heights, nums, 0, nums.size() - 1);
        vector<string> ret(n);
        for (int i = 0; i < n; i++) 
            ret[i] = names[nums[i]];
        return ret;
    }

    void QS(vector<int>& heights, vector<int>& nums, int l, int r) {
        if (l >= r) return; 
        int key = getkey(heights, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (heights[i] > key) {
                swap(heights[++left], heights[i]);
                swap(nums[left], nums[i++]);
            } else if (heights[i] == key) {
                i++;
            } else {
                swap(heights[--right], heights[i]);
                swap(nums[right], nums[i]);                
            }
        }
        QS(heights, nums, l, left);
        QS(heights, nums, right, r);
    }

    int getkey(vector<int>& heights, int l, int r) {
        int index = rand() % (r - l + 1) + l;
        return heights[index];
    }
};

// class Solution {
// public:
//     vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
//         vector<int> nums;
//         int n = heights.size();
//         for (int i = 0; i < n; i++)
//             nums.push_back(i);
//         QS(heights, names, 0, nums.size() - 1);
//         // vector<string> ret(n);
//         // for (int i = 0; i < n; i++) 
//         //     ret[i] = names[nums[i]];
//         return names;
//     }
//     void QS(vector<int>& heights, vector<string>& nums, int l, int r) {
//         if (l >= r) return; 
//         int key = getkey(heights, l, r);
//         int left = l - 1, right = r + 1, i = l;
//         while (i < right) {
//             if (heights[i] > key) {
//                 swap(heights[++left], heights[i]);
//                 swap(nums[left], nums[i++]);
//             } else if (heights[i] == key) {
//                 i++;
//             } else {
//                 swap(heights[--right], heights[i]);
//                 swap(nums[right], nums[i]);                
//             }
//         }
//         QS(heights, nums, l, left);
//         QS(heights, nums, right, r);
//     }
//     int getkey(vector<int>& heights, int l, int r) {
//         int index = rand() % (r - l + 1) + l;
//         return heights[index];
//     }
// };

class Solution03 {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> ret(n), index1(n), index2(n);
        for (int i = 0; i < n; i++)
            index1[i] = i, index2[i] = i;
        
        sort(index1.begin(), index1.end(), [&](int x, int y){
            return nums1[x] < nums1[y];
        });

        sort(index2.begin(), index2.end(), [&](int x, int y){
            return nums2[x] < nums2[y];
        });        

        // for (int i = 0; i < n; i++)
        //     cout << nums1[index1[i]] << " ";

        // int i = 0, j = 0;
        // while (i < n) {
        //     if (nums1[index1[i]] <= nums2[index2[j]]) {
        //         ret[n - i - 1] = nums1[i];
        //     } else {
        //         ret[i] = nums1[i];
        //         j++;
        //     }
        //     i++;
        // }
        
        // int left1 = 0, right = n - 1, left2 = 0;
        // while (left1 <= right) {
        //     if (nums1[index1[left1]] <= nums2[index2[left2]]) {
        //         ret[index2[right]] = nums1[left1];
        //         right--;
        //     } else {
        //         ret[index2[left1]] = nums1[left1];
        //         left2++;
        //     }
        //     left1++;
        // }
        int i = 0, left = 0, right = n - 1;
        while (i < n) {
            if (nums1[index1[i]] <= nums2[index2[left]]) {
                ret[index2[right]] = nums1[index1[i]];
                i++;
                right--;   
            } else {
                ret[index2[left]] = nums1[index1[i]];
                left++;
                i++;
            }         
        }

        return ret;
    }
};

class Solution04 {
public:
    int longestPalindrome(string s) {
        // 统计字符的个数
        // 偶数一定可以组成
        // 奇数只能放入一个，其余的奇数都要减一
        unordered_map<char, int> hash;
        for (auto ch : s) 
            hash[ch]++;
        int ret = 0;
        for (auto& it : hash) {
            ret += it.second / 2 * 2;
        }

        if (ret != s.size()) ret++;
        return ret;
    }
};

class Solution05 {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        // vector<int> num;
        vector<int> ret(n + 1);
        // for (int i = 0; i <= n; i++) num.push_back(i);
        int left = 0, right = n;
        int i = 0;
        for (auto ch : s) {
            if (ch == 'I') {
                ret[i++] = left;
                left++;
            } else {
                ret[i++] = right;
                right--;
            }
        }
        ret[n] = left;
        return ret;
    }
};

class Solution06 {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int ret = 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0, ns = s.size(), j = 0, ng = g.size();
        while (i < ns && j < ng) {
            if (s[i] >= g[j]) {
                ret++;
                i++, j++;
            } else {
                i++;
            }
        }
        return ret;
    }
};

class Solution07 {
public:
    string optimalDivision(vector<int>& nums) {
        if (nums.size() == 1) return to_string(nums[0]);
        if (nums.size() == 2) {
            string ret = to_string(nums[0]);
            ret += "/";
            ret += to_string(nums[1]);
            return ret;
        }

        string ret = to_string(nums[0]);
        ret += "/(";
        for (int i = 1; i < nums.size() - 1; i++) {
            ret += to_string(nums[i]);
            ret += "/";
        }
        ret += to_string(nums.back());
        ret += ")";
        return ret;
    }
};

class Solution08 {
    using PII = pair<int, int>;
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 0;
        // vector<int> dp(n, 0);
        // for (int i = 1; i < n; i++)  {
        //     for (int j = 0; j < i; j++) {
        //         if (nums[j] + j >= i) {
        //             dp[i] = dp[j] + 1;
        //             break;
        //         }         
        //     }
        // }
        // return dp[n - 1];
        // int ret = 0;
        // int left = 0, right = 1;
        // int i = 0;
        // while (right < n) {
        //     int next = 0;
            
        //     for (int j = left; j < right; j++) {
        //         next = max(next, nums[j] + j);
        //     }

        //     ret++;
        //     left = right + 1;
        //     right = max(next, left);
        // }
        // return ret;
        // int ret = 0;
        // queue<PII> q;
        // q.push({nums[0], 0});
        // int i = 0;
        // while (!q.empty()) {
        //     int sz = q.size();
        //     ret++;
        //     while (sz--) {
        //         int e = q.front().first, index = q.front().second; q.pop();
        //         if (e + index >= n - 1) return ret;
        //         // if (e + index < i) continue;
        //         // if (e == 0) continue;
        //         for (int j = index + 1; j <= e + index && j < n; j++) {
                    
        //             i = max(i, nums[j] + j);
        //             q.push({nums[j], j});
        //         }
        //     }
        // }
        int left = 0, right = 0;
        int ret = 0;
        int next = 0;

        while (right < n) {
            if (next >= n - 1) return ret;
            ret++;
            for (int i = left; i <= right; i++) {
                next = max(next, nums[i] + i);
            }
            left = right + 1;
            right = next;
        }

        return ret;
    }
};

int main() {


    return 0;
}